use std::collections::{HashMap, HashSet};
use std::fs::File;
use std::io::{BufRead, BufReader};

pub fn count_provinces() -> String {
    let mut result: Vec<String>  = Vec::new();
    // 读取文件
    let file = File::open("district.json").expect("read file error");
    let reader = BufReader::new(file);
    // 处理每一套数据
    let mut current_batch: Vec<String> = Vec::new();
    let mut open_work: bool = false;
    for line in reader.lines(){
        let line: String = line.expect("Failed to read line");
        if line.contains(": {") && !open_work {
            open_work = true;
            continue;
        }else if line.contains("}") && open_work {
            open_work = false;
            let num = work(&current_batch);
            result.push(num.to_string());
            // 清空
            current_batch.clear();
            continue;
        }
        if open_work {
            current_batch.push(line);
        }
    }
    return result.join(",");
}

// 计算每次的结果
pub fn work(current_batch: &Vec<String>) -> u32{
    let mut graph: HashMap<&str, HashSet<&str>> = HashMap::new();
    // 构建邻接表
    for line in current_batch{
        if let Some((key, list)) = parse_line(&line){
            for city in list {
                graph.entry(key).or_insert(HashSet::new()).insert(city);
                graph.entry(city).or_insert(HashSet::new()).insert(key);
            }
        }
    }
    // DFS
    let num = dfs(graph);
    return num;
}

/// 解析单行
fn parse_line(entry: &str) -> Option<(&str, Vec<&str>)> {
    if let Some(pos) = entry.find(':') {
        let key = entry[..pos].trim();
        let list_str = entry[pos + 1..].trim();

        // 去掉引号和逗号
        let key = key.trim_matches('"');
        let list: Vec<&str> = list_str.trim_end_matches(',').trim_matches('[').trim_matches(']')
            .split(",")
            .map(|x| x.trim().trim_matches('"'))
            .collect();
        return Some((key, list));
    }
    None
}

fn dfs(graph: HashMap<&str, HashSet<&str>>) -> u32{
    let mut result: u32 = 0;
    // 是否访问记录
    let mut is_visit: HashMap<&str, bool> = HashMap::new();
    for city in graph.keys(){
        is_visit.insert(&city, false);
    }
    // work
    for city in graph.keys(){
        if is_visit[city] {
            continue;
        }
        result += 1;
        let mut stack: Vec<&str> = Vec::new();
        stack.push(city);
        // 如果栈顶还有元素
        while let Some(now_city) = stack.pop() {
            if is_visit[now_city] {
                continue;
            }
            is_visit.insert(now_city, true);
            if let Some(neighbor_city) = graph.get(now_city){
                for c in neighbor_city{
                    if !is_visit[c] {
                        stack.push(&c);
                    }
                }
            }
        }
    }
    return result;
}